Real-world systems, including online social networks, communication networks, railway networks, and the like, are commonly modeled as temporal graphs. A temporal graph includes vertices (nodes), each vertex representing an entity in a system, and edges between vertices, each edge representing a temporal relationship between vertices. Answering earliest-arrival queries in temporal graphs is one of the most fundamental studies with numerous applications, such as information diffusion and measuring temporal closeness centrality. As the size of a temporal graph increases, processing resources required to perform queries, and query execution times increase.